#include "linker_operator.h"
std::vector<int> travelList(ListNode *head) {
    ListNode *pCurrent = head;
    std::vector<int> res;
    while (pCurrent) {
        res.push_back(pCurrent->val);
        pCurrent = pCurrent->next;
    }
    return res;
}

int linkLength(ListNode *head) {
    int length = 0;
    ListNode *current = head;
    if (!current)
        return length;
    while (current) {
        current = current->next;
        length++;
    }
    return length;
}

ListNode *reverseListRec(ListNode *head) {
    if (!head)
        return head;
    ListNode *pCurrent = head;
    ListNode *pPreNode = nullptr;
    ListNode *pNext = head;
    while (pCurrent) {
        pNext = pCurrent->next;
        pCurrent->next = pPreNode;
        pPreNode = pCurrent;
        pCurrent = pNext;
    }
    return pPreNode;
}

ListNode *reverseList(ListNode *head) {
    if (head == nullptr || head->next == nullptr)
        return head;
    ListNode *tail = reverseListRec(head->next);
    head->next->next = head;
    head->next = nullptr;
    return tail;
};

ListNode *mergeTwoListsRec(ListNode *l1, ListNode *l2) {
    if (!l1)
        return l2;
    else if (!l2)
        return l1;
    else {
        ListNode *pHead = l1;
        if (l1->val > l2->val) {
            pHead = l2;
            pHead->next = mergeTwoLists(l1, l2->next);
        } else
            pHead->next = mergeTwoLists(l1->next, l2);
        return pHead;
    }
}

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    ListNode *prenode = new ListNode(-1);
    ListNode *head = prenode;
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            prenode->next = l1;
            l1 = l1->next;
        } else {
            prenode->next = l2;
            l2 = l2->next;
        }
        prenode = prenode->next;
    }
    prenode->next = l1 == nullptr ? l2 : l1;
    ListNode *pMerge = head->next;
    delete head;
    return pMerge;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *pKeepHeadA = headA;
    ListNode *pKeepHeadB = headB;
    while (pKeepHeadA != pKeepHeadB) {
        pKeepHeadA = pKeepHeadA ? pKeepHeadA->next : headB;
        pKeepHeadB = pKeepHeadB ? pKeepHeadB->next : headA;
    }
    return pKeepHeadA;
}

bool hasCycle(ListNode *head) {
    if (!head)
        return false;
    ListNode *slow = head;
    ListNode *faster = head->next;
    if (slow == faster)
        return true; // 单节点环
    bool flag = false;
    while (slow != faster) {
        slow = slow->next;
        if (faster && faster->next) {
            faster = faster->next->next;
            if (faster == slow) {
                flag = true;
                break;
            };
        }
    }
    return flag;
}

ListNode *getKthFromEnd(ListNode *head, int k) {
    ListNode *first = head;
    ListNode *second = head;
    int i = 0;
    while (k > 0 && second) {
        second = second->next;
        k--;
    }
    if (k > 0)
        return nullptr;

    while (second) {
        second = second->next;
        first = first->next;
    }
    return first;
}
ListNode *deleteDuplicates(ListNode *head) {
    if (!head)
        return head;
    else {
        ListNode *pCurrent = head;
        while (pCurrent->next) {
            if (pCurrent->next->val == pCurrent->val) {
                pCurrent->next = pCurrent->next->next;
            } else {
                pCurrent = pCurrent->next;
            }
        }
        return head;
    }
}

bool isPalindrome(ListNode *head) {
    int length = 0;
    int isPali = true;
    ListNode *pCurrent = head;
    while (pCurrent) {
        length++;
        pCurrent = pCurrent->next;
    }
    pCurrent = head;
    int half = length >> 1;
    ListNode *pSecond = head;
    for (int i = 0; i < half; i++) {
        pSecond = pSecond->next;
    }
    if (length % 2 == 1)
        pSecond = pSecond->next;
    std::stack<ListNode *> s;
    for (int i = 0; i < half; i++) {
        s.push(pCurrent);
        pCurrent = pCurrent->next;
    }

    for (int i = 0; i < half; i++) {
        pCurrent = s.top();
        s.pop();
        if (pCurrent->val != pSecond->val) {
            isPali = false;
            break;
        } else {
            pSecond = pSecond->next;
        }
    }
    return isPali;
}

ListNode *removeNthFromEnd(ListNode *head, int n) {
    if (!head)
        return nullptr;
    ListNode *pFirst = head;
    ListNode *pSecond = head;
    ListNode *pDeletePre = nullptr;
    while (n > 0 && pSecond) {
        pSecond = pSecond->next;
        n--;
    }

    if (n > 0)
        return head; // n太大走到链表末尾了
    while (pSecond) {
        pSecond = pSecond->next;
        pDeletePre = pFirst;
        pFirst = pFirst->next;
    }
    if (!pDeletePre)
        return pFirst->next;
    else
        pDeletePre->next = pFirst->next;
    return head;
}

ListNode *rotateRight(ListNode *head, int k) {
    if (!head || k == 0 || !head->next)
        return head;
    int n = 0;
    ListNode *pTail = head;
    ListNode *pCurrent = head;
    ListNode *pTailPre = nullptr;
    ListNode *pCircle = nullptr;
    while (pTail) {
        n++;
        pTailPre = pTail;
        pTail = pTail->next;
    }
    pTailPre->next = head;
    int advance = n - 1 - k % n;
    if (advance == n)
        return head;
    while (advance) {
        pCurrent = pCurrent->next;
        advance--;
    }
    pTail = pCurrent->next;
    pCurrent->next = nullptr;
    return pTail;
}

ListNode *entryNodeOfLoop(ListNode *pHead) {
    if (!pHead)
        return pHead;
    ListNode *pFast = pHead;
    ListNode *pSlow = pHead;
    ListNode *pLoop = nullptr;
    while (pSlow && pFast && pFast->next) {
        pSlow = pSlow->next;
        pFast = pFast->next->next;
        if (pSlow == pFast) {
            pLoop = pSlow;
            break;
        }
    }
    if (!pFast || !pFast->next)
        return pLoop;
    pFast = pHead;
    while (pFast && pFast != pSlow) {
        pFast = pFast->next;
        pSlow = pSlow->next;
        if (pFast == pSlow) {
            pLoop = pFast;
            break;
        }
    }

    return pLoop;
}

ListNode *mergeNode(ListNode *pNode1, ListNode *pNode2) {
    if (pNode1 && !pNode2)
        return pNode1;
    else if (!pNode1 && pNode2)
        return pNode2;
    else if (!pNode1 && !pNode2)
        return pNode1;
    else {
        if (pNode1->val < pNode2->val) {
            pNode1->next = mergeNode(pNode1->next, pNode2);
            return pNode1;
        } else {
            pNode2->next = mergeNode(pNode1, pNode2->next);
            return pNode2;
        }
    }
}

ListNode *sortList(ListNode *pHead, ListNode *pTail) {
    if (!pHead)
        return pHead;
    else if (pHead->next == pTail) {
        pHead->next = nullptr;
        return pHead;
    } else {

        ListNode *pSlow = pHead, *pFast = pHead;
        while (pFast != pTail) {
            pSlow = pSlow->next;
            pFast = pFast->next;
            if (pFast != pTail)
                pFast = pFast->next;
        }
        ListNode *pNode1 = sortList(pHead, pSlow);
        ListNode *pNode2 = sortList(pSlow, pTail);
        return mergeNode(pNode1, pNode2);
    }
}

ListNode *sortList(ListNode *head) { return sortList(head, nullptr); }

ListNode *mergeKLists1(std::vector<ListNode *> &lists) {
    ListNode *root;
    for (auto e : lists) {
        mergeTwoLists(root, e);
    }
    return root->next;
}
//  ListNode* reverseBetween(ListNode* head, int m, int n) { return nullptr; }
